package com.haidechizi.graph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Graph {

    private Vertex[] vertices;

    private int[][] adjMat;

    private int currentSize;

    public Graph(int size) {
        vertices = new Vertex[size];
        adjMat = new int[size][size];
    }

    public void addVertex(Vertex vertex) {
        this.vertices[currentSize++] = vertex;
    }

    public void addEdge(String v1, String v2) {
        addEdge(v1, v2, 1);
    }

    public void addEdge(String v1, String v2, int weight) {
        int index1 = getIndex(v1);
        if (index1 == -1) {
            throw new RuntimeException("顶点" + v1 + "不存在");
        }
        int index2 = getIndex(v2);
        if (index1 == -1) {
            throw new RuntimeException("顶点" + v2 + "不存在");
        }
        adjMat[index1][index2] = weight;
        adjMat[index2][index1] = weight;
    }

    public int getIndex(String value) {
        for (int i = 0; i < vertices.length; i++) {
            if (vertices[i].getValue().equals(value)) {
                return i;
            }
        }
        return -1;
    }

    public void deepSearch() {//dfs
        if (vertices == null || vertices.length == 0) {
            return;
        }
        int index = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        vertices[0].visited = true;
        System.out.println(vertices[0].getValue());
        out:
        while (!stack.isEmpty()) {
            for (int i = index + 1; i < vertices.length; i++) {
                if (adjMat[index][i] == 1 && vertices[i].visited == false) {
                    stack.push(i);
                    vertices[i].visited = true;
                    System.out.println(vertices[i].getValue());
                    continue out;
                }
            }
            stack.pop();
            if (!stack.isEmpty()) {
                index = stack.peek();

            }

        }

    }


    public void breadFirstSearch() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        while (!queue.isEmpty()) {
            final Integer poll = queue.poll();
            System.out.println(vertices[poll].getValue());
            for (int i = poll + 1; i < vertices.length; i++) {
                if (adjMat[poll][i] == 1 && vertices[i].visited == false) {
                    queue.add(i);
                    vertices[i].visited = true;
                }
            }
        }

    }

}
